package Test_1113;

import Test_1106.MySingleList;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
public class Solution {
    //合并有序列表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pHead=new ListNode(-1);
        ListNode tmp=pHead;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                tmp.next=list1;
                tmp=tmp.next;
                list1=list1.next;
            }else{
                tmp.next=list2;
                tmp=tmp.next;
                list2=list2.next;
            }
        }
        if(list1!=null){
            tmp.next=list1;
        }
        if(list2!=null){
            tmp.next=list2;
        }
        return pHead.next;
    }
    //将所有小于x的结点排在其余结点之前
    public MySingleList.ListNode partition(MySingleList.ListNode pHead, int x) {
        MySingleList.ListNode headA=null;
        MySingleList.ListNode head1=null;
        MySingleList.ListNode headB=null;
        MySingleList.ListNode head2=null;
        MySingleList.ListNode tmp=pHead;
           while(tmp!=null) {
               if(tmp.val<x){
               if(headA==null){
                   headA=head1=tmp;
               }else{
                   head1.next=tmp;
                   head1=head1.next;
               }
               }else {
                   if (headB == null) {
                       headB = head2 = tmp;
                   } else {
                       head2.next = tmp;
                       head2 = head2.next;

                   }
               }
               tmp=tmp.next;
           }
           if(headA==null){
               return headB;
           }
           head1.next=headB;
        if(head2!=null){
            head2.next=null;
        }
           return headA;
    }

    public static void main(String[] args) {
        MySingleList list1=new MySingleList();
        list1.addLast(1);
        list1.addLast(3);
        list1.addLast(1);
        list1.addLast(2);
        list1.addLast(4);
        MySingleList list2=new MySingleList();

        list1.addLast(4);
        Solution solution=new Solution();
        solution.partition(list1.head,3);
    }
}
